1. Field of the Invention
The present invention relates to a common key encrypting process and more particularly to an encrypting apparatus with countermeasures for preventing decoding by a method so-called “power analysis attack”.
2. Description of the Related Art
An encrypting method is roughly divided into two of a public key cryptography and a common key cryptography. The public key cryptography uses different keys for encryption and decryption and ensures security by generally opening a key for encryption (public key) but opening a key for decrypting cipher text (private key) only to a receiver. However, the common key cryptography uses the same key for encryption and decryption (secret key) and ensures security using information unknown to a third party other than a transmitter and a receiver as this secret key.
There is one technology called “cryptanalysis” in the encryption field. The cryptanalysis is used to estimate private information, such as a private key or the like from available information, such as cipher text or the like and various methods are used for it. One method of them, which has been recently focused, is called “power analysis attack”.
The power analysis attack is devised by Paul Kocher in 1998. The power analysis attack estimates key information inside the encryption processor by collecting/analyzing power consumption data generated when various pieces of data are inputted to an encryption processor built in equipment, such as a smart card or the like. It is known that both a private and secret key can be estimated from the encrypting processor in both public key cryptography and common key cryptography.
There are two types of simple power analysis (hereinafter called “SPA”) and differential power analysis (hereinafter called “DPA”) in the power analysis attack.
The SPA estimates a private or secret key on the basis of the features of single piece of power consumption data in the encrypting processor. The DPA estimates a private or secret key by analyzing the difference among many pieces of power consumption data. Generally it is said that the DPA is stronger than the SPA.
The following Non-patent reference 1 discloses cryptanalysis for public key cryptography, such as Rivest-Shamir-Adleman (RSA) or the like by using SPA and DPA. Non-patent reference 2 discloses cryptanalysis using SPA and DPA for data encryption standards (DES) currently used as a standard in the common key cryptography. Non-patent reference 3 points out that Rijndael, which is common key cryptography that seems to be used as a standard in the next generation may be analyzed by using the DPA.
As described above, cryptanalysis using DPA as the power analysis is focused for the reason that it is especially effective and various analyzing methods are studied. Not only cryptanalysis but also countermeasure technology for preventing the analysis by DPA are developed and are focused as a technology important as much as cryptanalysis.
FIG. 1 shows the general configuration of the common key encrypting process. Generally, the common key encrypting process is composed of two processes of extended key generation 1501 and round processing 1502. In the extended key generation 1501, a plurality of pieces of data called “extended keys” (extended key 0, extended key 1, . . . , extended key N) are generated from an inputted secret key and they are outputted to the round processing 1502. When inputting these extended keys and plain text to the round processing 1502, conversion for encrypting is performed and cipher text is outputted.
As the algorithm of a typical common key encrypting, advanced encryption standards (AES) are known and are published as the standard Federal Information Processing Standards Publication 197 (FIPS197) of National Institute of Standards and Technology (NIST) in U.S.A (for example, see the following Non-patent reference 4).
FIG. 2 shows the configuration of AES. AES is an algorithm using 128 bits as an encrypting unit. Specifically, 128-bit cipher text is generated from 128-bit plain text. A secret key can be one of three types; 128, 192 or 256 bits.
Firstly, when performing extended key generation 1601, (N+1) 128-bit extended keys are generated from a secret key. The round processing 1602 of AES is composed of four types of Round Key 1611, Sub-byte 1612, Shift Row 1613 and Mix-Column 1614. The extended keys are used in the Round Key 1611 of these. When plain text is inputted to the round processing 1602, the processes, the Round Key 1611, the Sub-byte 1612, the Shift Row 1613 and the Mix-Column 1614 are repeated (N−1) times in this order.
Then, processes, Round Key 1615, Sub-byte 1616, Shift Row 1617 and Round Key 1618 are performed to output cipher text. The number N of times of repetition varies depending on the bit length of a secret key. When it is 128, 192 and 256 bits, N=10, 12 and 14, respectively.
In the Round Key process, as shown in FIG. 3, the exclusive logical OR (XOR) of 128 bits of input data and 128 bits of extended key is calculated and outputted as output data. In the Sub-byte process, as shown in FIG. 4, 128 bits of input data is converted into 128 bits of output data by the same 16 non-linear conversion tables (S-boxes) 1801-1˜1801-16.
In the Shift Row process, as shown in FIG. 5, input data X composed of 16 8-bit data xj (j=0, 1, . . . , 15) is converted into output data X composed of 16 8-bit data yi (i=0, 1, . . . , 15) by the following equation.yi=xj, j=13i−4(mod 16)  (1)
In equation (1), (mod 16) indicates residue calculation modulo 16.
In the Mix-Column process, as shown in FIG. 6, output data composed of 16 pieces of 8-bit data yi is generated from input data composed of 16 pieces of 8-bit data xj (j=0, 1, . . . , 15). In this case, the following multiplication is performed using four multipliers 2001-1˜2001-4.
                                          (                                                                                y                                                                  4                        ⁢                        i                                            +                      3                                                                                                                                        y                                                                  4                        ⁢                        i                                            +                      2                                                                                                                                        y                                                                  4                        ⁢                        i                                            -                      1                                                                                                                                        y                                          4                      ⁢                      i                                                                                            )                    =                                    (                                                                    02                                                        03                                                        01                                                        01                                                                                        01                                                        02                                                        03                                                        01                                                                                        01                                                        01                                                        02                                                        03                                                                                        03                                                        01                                                        01                                                        02                                                              )                        ⁢                          (                                                                                          x                                                                        4                          ⁢                          i                                                +                        3                                                                                                                                                        x                                                                        4                          ⁢                          i                                                +                        2                                                                                                                                                        x                                                                        4                          ⁢                          i                                                -                        1                                                                                                                                                        x                                              4                        ⁢                        i                                                                                                        )                                      ⁢                                  ⁢                              i            =            0                    ,          1          ,                      2            ⁢                                                  ⁢            and            ⁢                                                  ⁢            3                                              (        2        )            
Equation (2) shows a calculation process operated by each of the four multipliers 2001-1˜2001-4 included in the Mix-Column process shown in FIG. 6.
Next, a secret key analyzing method by DPA is described. The DPA is a method for analyzing a secret key by measuring power consumption of the round processing 1502 shown in FIG. 1. The configuration of a common key encrypting process for analyzing by using DPA is described below without limiting it to AES.
In a general common key encrypting method, round processing is configured by combining three of an extended key XOR process shown in FIG. 7, a linear conversion process shown in FIG. 8 and a non-linear conversion process shown in FIG. 9, and the round processing is repeatedly performed a plurality of times.
As shown in FIG. 7, the extended key XOR process outputs the XOR operation result Z of input data X and an extended key K. As shown in FIG. 8, the linear conversion process outputs Z that satisfies Z=L(X), to the input data X. If XOR operation is described ⊕, L indicates linear conversion that satisfies the flowing equation as to arbitrary X and Y.L(X⊕Y)=L(X)⊕L(Y)  (3)
More specifically, the bit permutation process, such as the Shift Row process shown in FIG. 5, matrix operation, such as the Mix-Column process shown in FIG. 6 and the like correspond to L.
As shown in FIG. 9, the non-linear conversion process outputs Z that satisfies Z=W(X), to the input data X. In this case, W indicates non-linear conversion that does not satisfy the following equation (4) as to arbitrary X and Y.W(X⊕Y)=W(X)⊕W(Y)  (4)
More specifically, it often realizes W by a non-linear conversion index called “S-box”. In this case, input data X is divided into u pieces like X=x0x1 . . . xu-1 and zj expressed by zj=wj(xj), using wj (j=0, 1, . . . , u-1) indicating an S-box is calculated. Then, they are combined again like Z=z0z1 . . . zu-1 and the obtained data Z is outputted.
Next, a analyzing method applying DPA to a common key encrypting process obtained by combining the above-described processes is described. Here, as the simplest example, it is shown that an extended key K can be analyzed by applying DPA to the process shown in FIG. 10 obtained by combining the process shown in FIG. 7 and that shown in FIG. 9. The process shown in FIG. 10 is equivalent of a process obtained by combining the Round Key process in AES (FIG. 3) and the Sub-byte process (FIG. 4).
FIG. 11 shows a configuration obtained by extracting only bits related to the input/output of wj from the configuration shown in FIG. 10. In FIG. 11, it is assumed that mj, kj and wj indicate a known value mj, such as plain text or the like, an unknown value kj, such as extended key, and a known S-box wj. It is shown that an extended key kj can be estimated by DPA under this condition.
DPA is composed of two steps of the measurement of power consumption data and the analysis of an extended key using differential power. In the measurement of power consumption data, if an oscilloscope or the like is used, power consumption data consumed by an encrypting processor when specific plain text is inputted can be measured as the power consumption curve shown in FIG. 12. Such a measurement is repeated while changing the value of plain text and when measurement data is obtained over sufficient times, the measurement is terminated. The aggregate of power consumption curves obtained in this series of measurements is assumed to be G.
Next, the analysis of an extended key using the power consumption curve is described. Firstly, as to an extended key kj used inside the encrypting process it is assumed that kj=k′j. Since mj and wj are already known, the aggregate G can be classified into the following two types of G0(k′j) and G1(k′j), on the basis of this k′j assumption.G0(k′j)={G|the e-th bit value of zj=wj(mj⊕k′j)=0}  (5)G1(k′j)={G|the e-th bit value of zj=wj(mj⊕k′j)=1}  (6)
Then, the following differential power curve DG(k′j) is generated.DG(k′j)=(Average of power consumption curve belonging to aggregate G1)−(Average of power consumption curve belonging to aggregate G0)  (7)
If this assumption is correct, that is, k′j=kj, a spike shown in FIG. 13 appears on the differential power curve DG(k′j), If this assumption is wrong, that is, k′j≠kj, the differential power curve DG(k′j) becomes a flat curve with no spikes as shown in FIG. 14. Therefore, if the differential power curve shown in FIG. 13 is obtained from assumed k′j, the extended key kj can be analyzed.
If such kj analyzing is applied to each j, lastly, the extended key K shown in FIG. 10 can be analyzed. By repeatedly applying this analysis to the extended key 0, the extended key 1, . . . , the extended key N, the secret key can be decoded. In the case of AES, since the leading value of an extended key is the value of the secret key value without performing any process from the nature of the algorithm, the entire secret key can be analyzed if the extended key 0 is analyzed when the secret key is 128 bits and if the extended keys 0 and 1 are analyzed when the secret key is 192 or 256 bits.
Next, the reason why spikes appear on the differential power curve DG(k′j) when k′j=kj is described. If k′j=kj, as to zj, the following equation holds true by classifying G into G0(k′j) and G1(k′j) according to equations (5) and (6).(Average Hamming weight of zj belonging to G1)−(Average Hamming weight of zj belonging to G0)=1  (8)
If k′j≠kj, equation (8) does not hold true. In this case, since random classification is performed, the following equation holds true.(Average Hamming weight of zj belonging to G1)−(Average Hamming weight of zj belonging to G0)=0  (9)
In the above equation, the Hamming weight is the number of a bit value ‘1’ included in a bit array when a specific value is expressed by the bit array. For example, the Hamming weight of a bit value (1101)2 is 3.
When equation (8) holds true, there is a difference in the average Hamming weight of a load value zj between G1(k′j) and G0(k′j). However, when equation (9) holds true, there is no difference in the average Hamming weight of a load value zj between G1(k′j) and G0(k′j).
Generally it is considered that power consumption is in proportion to the Hamming weight of a data value. The following Non-patent reference 5 shows an experimental result indicating that this is correct. Therefore, if k′j=kj, the difference of power consumption appears on the differential power curve as a spike since equation (8) is satisfied. However, in the case of equation (9), no spikes appear and the differential power curve becomes flat.
Although so far DPA applied to the simplest configuration shown in FIG. 10 has been described, it is found that such a analyzing method is effective even when the linear conversion shown in FIG. 8 is inserted.
FIG. 15 shows the generalized configuration shown in FIG. 10 and two linear conversion processes L1 and L2 are inserted before and after the extended key XOR process. For example, if a function for outputting input without performing any process, a bit permutation function and an S-box called “B function of SC2000” are L1, L2 and wj, respectively, FIG. 15 shows a configuration equivalent of SC2000.
The following Non-patent reference 6 discloses the specification of SC2000. Since L2 is a bit permutation function, the process shown in FIG. 15 can be converted into the same process shown in FIG. 11 if it is a configuration obtained by extracting only bits related to the input/output of wj. Therefore, the extended key K can be decoded using the same DPA as described above.
Although in the above-described method, the S-box output in the non-linear process is focused and DPA is applied, besides it, a method of focusing the value immediately after the XOR operation of the input mj and the key kj (output value of extended key XOR process) and the value of the value xj inputted to the S-box and applying DPA is known (for example, see the following Non-patent reference 7).
If the above descriptions are put in order, a secret key can be analyzed by DPA when the following conditions are met.
DPA-1: If the input M is known and controllable, the key K is unknown and fixed, and the conversion of the wj of the S-box is known, the secret key K can be analyzed by measuring the power consumption curve of the part A shown in FIG. 16 (output of the wj of the S-box).
DPA-2: If the input M is known and controllable, the key K is unknown and fixed, the secret key K can be analyzed by measuring the power consumption curve of the part B shown in FIG. 16 (writing of the output value of the extended key XOR process).
DPA-3: If the input M is known and controllable, the key K is unknown and fixed, the secret key K can be analyzed by measuring the power consumption curve of the part C shown in FIG. 16 (loading of an input value in order to index the wj of the S-box).
The following Patent reference 1 also discloses these DPA attack conditions.
As the power consumption measurement method for applying DPA, two methods are known. In one method, as shown in FIG. 17, a resistor 3102 is connected to the surface of a smart card 3101, and the voltage between both ends of the resistor 3102 is measured by an oscilloscope 3103. The other method, as shown in FIG. 18, measures power consumption by installing an electro-magnetic wave probe 3201 connected to the oscilloscope 3103 on the surface of the smart card 3101 and measuring an electro-magnetic wave leaked from the smart card 3101.
The method shown in FIG. 17 has an advantage that it requires an attacker of little labor since it is sufficient to simply attach a resistor to the surface of the card. However, since it measures the power consumption of the entire card, it also measures power consumption not related to the encrypting process, which is a disadvantage.
The method shown in FIG. 18 has an advantage that its measurement accuracy is high since it can partially measure the power consumption of the card. For example, when the smart card 3101 comprises a central processing unit (CPU), random-access memory (RAM), read-only memory (ROM), an operator and an encrypting processor, the power consumption of the encrypting process can be intensively measured while suppressing the respective power consumption factors of the CPU, RAM, ROM and the operator at a low level by installing an electro-magnetic wave probe 3201 near the encrypting processor. This is because the nearer the location of the electro-magnetic wave probe 3201 is from the current source, the stronger the electro-magnetic wave becomes since the intensity of the electro-magnetic wave is in inverse proportion to the square of its distance from a current source.
By carefully selecting the location of the electro-magnetic wave probe 3201, the power consumption of only the round processing 1502 can also be measured, for example, without measuring the power consumption of the extended key generation 1501 shown in FIG. 1. However, since the power measurement experiments must be repeated a lot if times in order to find the optimal location of the electro-magnetic wave probe 3201, it takes a high time cost, which is a disadvantage.
Next, the conventional DPA countermeasures are described with reference to FIGS. 19-21. As the DPA countermeasures, there are a method of reducing the measurement accuracy of the amount of power consumption by inserting a noise generator in the smart card or the like and a method of applying countermeasures to the encrypting process and randomizing power consumption. The former can be easily implemented. However, since the key can be analyzed, for example, by using the power measurement method shown in FIG. 18, it cannot be its basic countermeasures. However, although the latter cannot be easily implemented, it can be its basic countermeasures.
As a typical method of randomizing power consumption, a method (hereinafter called “Conventional method 1”) called “masking method” is known (for example, see the following Non-patent reference 8). If data to be calculated in the encrypting process without DPA countermeasures is M, in the Conventional method 1, the encrypting process is performed by calculating data M′ and R expressed by the following equation instead of the data M.M′=M⊕R  (10)
In the above equation, R is a random number and is generated every time the encrypting process is performed. According to this method, the data M′ is masked by XOR-operating the random value R for the data M of the encrypting process. Since power consumption can be randomized by randomizing data, the secure processing against DPA can be realized. Hereinafter, a value to be XOR-operated for data without DPA countermeasures is called “mask value”. (In the above equation, R is mask value.)
Since in this method, the operation must be applied to each of two pieces of data, M′ and R at each stage of the round processing, according to the value of the random number R, it has a problem that its process time is double or more, compared with the case where data M is directly calculated.
Problem 1: Since the calculation of the encrypting process must be duplicated, its process time is double or more.
The above-described Patent reference 1 discloses a method for solving this problem (hereinafter called “Conventional method 2”). While in Conventional method 1, a mask value is generated at random, in Conventional method 2, one is selected from a plurality of fixed values calculated in advance by a random number and is used as a mask value. If the selected mask value is expressed as Rx, in Conventional method 2, data M′x and Rx that satisfy the following equation are calculated.M′x=M⊕Rx  (11)
In the above equation, since Rx is calculated in advance, there is no need to calculate both M′x and Rx and it is sufficient to calculate only M′x. Therefore, in Conventional method 2, there is no need to duplicate the calculation as in Conventional method 1, thereby realizing a high-speed process.
By using the DPA countermeasures of Conventional method 2, the encrypting process without DPA countermeasures shown in FIG. 10 can be replaced with the encrypting process shown in FIG. 19. FIG. 19 shows the configuration in which the process shown in FIG. 10 is regarded as the combination of the Round Key process and Sub-byte process in AES.
In FIG. 19, selectors 3301-j and 3306-j (j=0, 1, . . . , 15) ((q−1) MUX) selects one from q pieces of input data according to a random number and outputs it. A demultiplxer 3304-j (j=0, 1, . . . , 15) ((q−1) DEMUX) outputs the inputted data to an output destination selected from q output destinations according to a random number.
An XOR operator 3302-j masks Kj by calculating the XOR of Kj extended keys K0-K15 divided every 8 bits and a value selected from constants c0-cq-1 by the selector 3301-j. The XOR operator 3303-j calculates the XOR of the masked extended key and the input data.
Then, a non-linear conversion process by an S-box circuit 3305-j is applied to the operation result of the XOR operator 3303-j. In this process, one is selected from q pieces of S-boxes (S′0[x]-S′q-1[x]) according to a random number, and the input data is converted using the S-box. The random number used for this selection is the same as the random number used to select the mask value of the extended key Kj.
Each of S′0[x]-S′q-1[x] is masked with each of different constants d0-dq-1. Specifically, if an S-box without DPA countermeasures is S[x], S′i[x] (i=0, 1, . . . , q−1) is expressed as follows.S′i[x]=S[x⊕ci]⊕di  (12)
Since there is the demultiplexer 3304-j on the input side of the S-box circuit 3305-j and the selector 3306-j on the output side, the signal of the extended key XOR operation transmits only one of the q pieces of S-boxes. Since the respective logic of q pieces of S-boxes is different, its power characteristic is also different. Therefore, by selecting one from these by a random number, power consumption is randomized and the secure processing against DPA can be realized.
Since this method directly randomizes the power consumption of the round processing 1502 shown in FIG. 1, secure processing by both the power measurement methods shown in FIGS. 17 and 18 can be realized. However, the configuration shown in FIG. 19 requires q times of S-boxes without DPA countermeasures. Generally, since the circuit area of an S-box is very large, the DPA countermeasures shown in FIG. 19 have the following problem.
Problem 2: Since it requires q times of S-boxes without DPA countermeasures, its circuit area becomes large.
As a method for solving this problem, the DPA countermeasures disclosed by the following Patent reference 2 are known (hereinafter called “Conventional method 3”). This method randomizes the power consumption of the extended key generation 1501 shown in FIG. 1. In order to describe this mechanism, the extended key generation in AES, without DPA countermeasures is described below.
In the extended key generation in AES, a Sub-byte process is performed as in the round processing. In this case, as shown in FIG. 20, a Sub-byte process by a 32-bit unit is performed. In Conventional method 3, the circuit shown in FIG. 21 is used to randomize the power consumption of the Sub-byte process shown in FIG. 20.
The circuit shown in FIG. 21 comprises four S-boxes (S0-S3) and route selection circuits 3501 and 3502 for selecting the route of input data X according to a random number. 32-bit data X is divided into four pieces of 8-bit data x0-x3, which are inputted to the route selection circuit 3501. When they are inputted to the route selection circuit 3501, data is arranged in the order of x0, x1, x2 and x3. However, when they are outputted, this order is re-arrayed at random according to a random number. In FIG. 21, they are re-arrayed in the order of x1, x3, x0 and x2 when viewed from the highest-order bit.
After the data order is changed, each of S-box processes expressed as S0-S3 is applied to these pieces of data. Although these S-boxes are logically the same as S-boxes without DPA countermeasures, they are mounted in a physically different form each other. Therefore, their power consumption characteristics are different each other. For example, S0 is mounted as a logical circuit, S1 is mounted as static random-access memory (SRAM), S2 is mounted as mask ROM and S3 is mounted as flash ROM.
Specifically, since an S-box that processes data xj (j=0, 1, 2 and 3) is selected from S0-S3 at random, power consumption changes at random. Therefore, DPA security can be improved. After the calculation by an S-box is completed, the route selection circuit 3502 changes the data order and restores the order of data randomized when inputted to the S-box.
This configuration has an advantage that it is superior to the configuration without DPA countermeasures shown in FIG. 20 in the using efficiency of a circuit area. While in Conventional method 2 shown in FIG. 19, only one of q pieces of S-boxes is used for the encrypting process, in Conventional method 3, all S-boxes are used for the encrypting process thanks to the function of the route selection circuit. Therefore, Conventional method 3 can solve Problem 2 of Conventional method 2.
Patent reference 1: Japanese Patent Application Publication No. 2002-366029
Patent reference 2: Domestic publication of PCT International Patent Application No. 2005-527853
Non-patent reference 1: Thomas S. Messerges, Ezzy A. Dabbish and Robert H. Sloan, “Power Analysis Attacks of Modular Exponentiation in Smart Cards”, Cryptographic Hardware and Embedded Systems (CHES '99), Springer-Verlag, pp. 144-157 (1999).
Non-patent reference 2: Paul Kocher, Joshua Jaffe and Benjamin Jun, “Differential Power Analysis”, in proceedings of Advances in Cryptology-CRYPTO '99, Spring-Verlag, pp. 388-397 (1999).
Non-patent reference 3: Chari C. Jutla, J. R. Rao and P. Rohatgi, “A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards”, Second Advanced Encryption Standard Candidate Conference, February 1999.
Non-patent reference 4: “Federal Information Processing Standards Publication 197”, [online], [retrieved Oct. 2, 2006], The Internet<URL: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf>
Non-patent reference 5: T. S. Messerges, Ezzy A. Dabbish and Robdert H. Sloan, “Investigations of Power Attacks on Smart Cards”, in Proceedings of USENIX Workshop on Smart-Card Technology, May 1999.
Non-patent reference 6: Takeshi Shimoyama, Hitoshi Yanami, Kazuhiro Yokoyama, Masahiko Takenaka, Koichi Itoh, Jun Yajima, Naoya Toriii and Hidema Tanaka, “The Block Cipher SC2000”, Fast Software Encryption (FSE 2001), pp. 312-327, LNCS vol. 2355 (2002)
Non-patent reference 7: M. Akkar, R. Bevan, P. Dischamp and D. Moyart, “Power Analysis, What Is Now Possible . . . ”, ASIACRYPT 2000, pp. 489-502 (2000).
Non-patent reference 8: Thomas S. Messerges, “Securing the AES Finalists Against Power Analysis Attacks”, in Proceedings of Fast Software Encryption Workshop 2000, Spring-Verlag, pp. 150-164 (2001).
The above-described DPA countermeasures of Conventional method 3 have the following two new problems. The first problem is as follows.
Problem 3: Since Conventional method 3 randomizes only the power consumption of extended key generation, DPA security is low. Specifically, although the method shown in FIG. 17 can prevent DPA from measuring the power consumption of the entire smart card, the method shown in FIG. 18 cannot prevent DPA from measuring the power consumption of a part of the circuit of a smart card.
As described above, DPA analyzes a secret key by measuring the power consumption of the round processing 1502 shown in FIG. 1. However, although Conventional method 3 can randomize the power consumption of the extended key generation 1502, it cannot randomize the power consumption of the round processing 1502.
Therefore, the security of DPA for measuring the power consumption of the entire smart card is high. However, the security of DPA for measuring the power consumption of the part of the smart card is low since only the power consumption of the round processing 1502 can be measured.
Conventional method 3 further has the following problem.
Problem 4: Since the route selection circuit of Conventional method 3 requires a circuit for generating a selection signal from an inputted random number in addition to a selector circuit and a demultiplexer circuit, its circuit scale becomes large.
In order to describe this problem, an example of the configuration of the route selection circuit of Conventional method 3 is shown in FIG. 22. FIG. 22 shows the configuration shown in FIG. 11 of the above-described Patent reference 2. It comprises a selection signal generation circuit 3601 and route selection circuits 3602 and 3603. The selection signal generation circuit 3601 comprises a random number decoder 3611 and an inverter circuit 3612. The route selection circuit 3602 comprises selectors (4-1 MUX) 3621-1˜3621-4 and the route selection circuit 3603 comprises 4-input/1-output selectors 3622-1˜3622-4.
A random number generator, which is not shown in FIG. 22, generates 9-bit random number. When this random number is inputted to the random number decoder 3611, the random number decoder 3611 outputs an 8-bit signal, This 8-bit signal is inputted to the route selection circuit 3602 as a selection signal. A 2-bit selection signal is assigned to each of the selectors 3621-1˜3621-4 of the route selection circuit 3602. Each selector 3621-j (j=1, 2, 3 and 4) selects one from input signals x0-x3 according to this selection signal and outputs it.
In FIG. 22, the selectors 3621-1, 3621-2, 3621-3 and 3621-4 select x1, x3, x0 and x2, respectively. This selection operation is performed in such a way that an output signal may not overlap among the four selectors. This is because since if an output signal overlaps and, for example, selectors 3621-1, 3621-2, 3621-3 and 3621-4 select x0, x3, x0 and x2, respectively, the S-box process of x1 is not performed, a normal encrypting result cannot be obtained.
For example, of the four selectors shown in FIG. 22, the selector 3621-1 selects input signal x1, the other selectors 3621-2˜3621-4 never selects input signal x1.
It is by the function of the random number decoder 3611 that the overlap among x0-x3 can be avoided while generating a random selection signal according to a random number. Furthermore, the random number decoder 3611 also prevents the statistical bias of a random selection signal. Specifically, by enabling an S-box that processes xj to be selected from S0-S3 with equal probability 1/4, the statistical bias is prevented and the secure processing of DPA can be realized.
When S0, S1, S2 and S3 are applied to x1, x3, x0 and x2, respectively, as an S-box process, as a result, signals z1, z3, z0 and z2 are generated and inputted to the route selection circuit 3603.
The inverter circuit 3612 inverts the 8-bit signal outputted from the random number decoder 3611 and outputs the obtained signal to the route selection circuit 3603 as a selection signal. This selection signal is used to restore the order of the signal whose order the route selection circuit 3602 has changed at random to original one. Specifically, a selection signal for restoring the signal order from z1, z3, z0 and z2 to z0, z1, z2 and z3 is generated.
The 8 bits of the selection signal generated by the inverter circuit 3612 are divided into four of two bits and are one of them is inputted to each of the selectors 3622-1˜3622-4. Thus, the selectors 3622-1˜3622-4 select z0, z1, z2 and z3, respectively.
By adopting the configuration shown in FIG. 22, power consumption can be randomized without increasing the number of S-boxes. However, since in order to realize the secure processing of DPA, a random number cannot be directly inputted to the route selection circuits 3602 and 3603, the selection signal generation circuit 3601 comprising the random number decoder 3611 and the inverter circuit 3612 is needed. As a result, the above-described Problem 4 occurs.
It has been found that according to Problem 1, Conventional method 1 takes two times of processing time, according to Problem 2, Conventional method 2 requires q times of S-boxes, according to Problem 3, DPA is not effective on Conventional method 3 shown in FIG. 18 since it cannot randomize the power consumption of the round processing and according to Problem 4, Conventional method 3 requires a selection signal generation circuit. Therefore, a method for solving these problems simultaneously is studied below.
FIG. 23 shows the configuration of an encrypting circuit obtained by simply combining Conventional methods 2 and 3. This encrypting circuit comprises XOR operators 3701-0˜3701-3 and 3702-0˜3702-3, selectors 3703-0˜3703-3, a selection signal generation circuit 3704, route selection circuits 3705 and 3706, and four Sboxes (S0˜S3). The selection signal generation circuit 3704 comprises an inverter circuit 3711 and a random number decoder 3712.
The operations of the XOR operators 3701-j and 3702-j and selector 3703-j (j=0, 1, 2 and 3) are the same those of the XOR operators 3302-j and 3303-j and selector 3301-j shown in FIG. 19. The operations of the selection signal generation circuit 3704, route selection circuits 3705 and 3706 and S0-S3 are the same as those of the selection signal generation circuit 3601, route selection circuits 3602 and 3603 and S0-S3 shown in FIG. 22.
32 bits of data M are divided into four pieces of 8-bit data m0-m3 and are inputted to this encrypting circuit. Eight bits of extended key K0-K3 and random numbers r0-r3 and r are also inputted to it. If xj indicates the XOR of mj and Kj and an S-box without DPA countermeasures is S, Sj[X]=S[x]. crj indicates a mask value selected from constants c0-c3 by a random number rj.
In order to solve Problem 3, in this configuration, the power consumption of each of the Round Key process and Sub-byte process in AES is randomized. The power consumption of the Round Key process is randomized by Conventional method 2 and that of the Sub-byte process is randomized by Conventional method 3. By using Conventional method 3 for the Sub-byte process in AES, Problem 2 can be also solved.
However, this configuration has a problem that it does not meet the data processing conditions of the mask method. As described as to Conventional method 2 shown in FIG. 19, the data processing conditions of the mask method is that calculated data T′ can be expressed as follows, using a mask value Rx selected by a random number.T′=T⊕Rx  (13)
If this Rx is determined only by a random number without depending on T and T′, T′ can be simply restored to the original T according to the following equation after all AES encrypting process is completed.T=T′⊕Rx  (14)
If Rx depends on T and T′, Rx must be dynamically calculated according to T′. Since calculation must be duplicated in order to perform this calculation, Problem 1 which Conventional method 2 should have essentially solved cannot be solved.
The reason why the configuration shown in FIG. 23 does not meet the data processing conditions of the mask method is that the Sub-byte process uses an unmasked S-box in the Round Key process although a constant selected by a random number performs a mask process. For example, if the Round Key process is applied to the eight highest-order bits m0 of input data, x0⊕cr0 is outputted. In this case, x0=m0⊕K0.
Then, an S-box by S2 is applied to the data x0⊕cr0 via the route selection circuit 3705 which changes data order according to a random number r, and S2[x0⊕cr0]=S[x0⊕cr0] is outputted. Then, the route selection circuit 3706 restores S[x0⊕cr0] to the position of the highest 8 bits and the data is outputted. In this case, S[x0⊕cr0] does not meet the data processing conditions of the mask method. This is because in T′=T⊕Rx, although T′=S[x0⊕cr0] and T=S[x0], S[x0⊕cr0]=S[x0]⊕S[cr0] is not satisfied and Rx=S[cr0] does not hold true since S is a non-linear conversion function. Specifically, Rx is not only determined by random number r0 but also is changed by the influence of data value x0.
A configuration for solving this problem is shown in FIG. 24. FIG. 24 shows the configuration in which Conventional method 3 is applied to the Sub-byte process in the round processing of AES. The Round Key process is the same as that without DPA countermeasures.
Since in the Round Key process, a mask by crj is not attached different from the configuration shown in FIG. 23, output data S[x0]-S[x3] can be obtained against input data m0-m3. Therefore, a process equivalent of that in the case where Rx=0 in T=T′⊕Rx can be realized.
However, in this configuration, although the power consumption of the Sub-byte process can be randomized, the power consumption of the Round Key process cannot be randomized. Specifically, although the power consumption of the input/output of the S-boxes indicated by C and A shown in FIG. 16 can be randomized, the power consumption of output of the XOR operation indicated by B cannot be randomized. Therefore, the security against DPA cannot be realized because of the weakness described as DPA-2.
Thus, by simply applying Conventional methods 2 and 3 to the round processing of AES, DPA countermeasures by which all the above-described Problems 1-4 can be solved cannot be realized.